// 567. 字符串的排列
// https://leetcode.cn/problems/permutation-in-string
// 中等，给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。
// 如果是，返回 true ；否则，返回 false 。
// 换句话说，s1 的排列之一是 s2 的 子串 。
// 示例 1：
// 输入：s1 = "ab" s2 = "eidbaooo"
// 输出：true
// 解释：s2 包含 s1 的排列之一 ("ba").
// 示例 2：
// 输入：s1= "ab" s2 = "eidboaoo"
// 输出：false

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        map<char,int> mpLetter;
        for(auto c:s1) mpLetter[c]++;
        for(int left=0,right=0; right<s2.length(); ) {
            char c = s2[right++];
            mpLetter[c]--;
            while(left<right && mpLetter[c]<0) {
                mpLetter[s2[left++]]++;
            }
            if (right-left == s1.size()) {
                return true;
            }
        }
        return false;
    }
};

